package org.feit.findword.trie;
import java.io.IOException;
import java.io.OutputStream;
import java.io.ByteArrayOutputStream;
import java.util.LinkedHashMap;

import android.util.Log;

/**
 * This is the base implementation of the Trie. It allows a trie to be created
 * and modified in memory and then written to a file in a compressed format. It
 * also contains methods that can be used to find all of the words on a board.
 */
public class TrieMk implements WordFilter {

	protected static final int LETTERS_COUNT = 31;
	protected static final long WORD_BIT = 0x100000000L;
	protected static final long LETTER_MASK = 0x7fffffffL;
	protected static final long LEAF_BIT = 0x200000000L;

	protected final TrieLeaf EMPTY_LEAF;
	protected final TrieLeaf WORD_LEAF;

	private int nodeCount;
	private int tailCount;

	protected TrieNode root;

	public TrieMk() {
		nodeCount = 0;

		EMPTY_LEAF = new TrieLeaf();
		WORD_LEAF = new TrieLeaf(WORD_BIT);
		root = EMPTY_LEAF;
	}

	public int getNodesCount() {
		return nodeCount;
	}

	public void addWord(String w) {
		long wordBits = 0;
		wordBits |= WORD_BIT;
		root = root.addSuffix(w, 0, wordBits);
	}

	public boolean isWord(String w) {
		long wordMask = 0;
		wordMask |= WORD_BIT;
		return root.isWord(w, 0, wordMask);
	}

	private static void writeLong(OutputStream out, long i) throws IOException {
		out.write((int) (i >> 32));
		out.write((int) (i >> 24));
		out.write((int) (i >> 16));
		out.write((int) (i >> 8));
		out.write((int) i);
	}

	private static void writeThree(OutputStream out, int i) throws IOException {
		out.write(i >> 16);
		out.write(i >> 8);
		out.write(i);
	}

	/**
	 * This is the base class for the Nodes that compose a Trie.
	 */
	protected class TrieNode {
		long childBits;

		TrieNode children[];

		TrieNode() {
			childBits = 0;
			children = new TrieNode[LETTERS_COUNT];

			nodeCount++;
		}

		TrieNode(long cBits) {
			this();
			childBits = cBits;
		}

		void writeNode(OutputStream out) throws IOException {

			ByteArrayOutputStream os = new ByteArrayOutputStream();

			int j = 0;
			for (long i = childBits & LETTER_MASK; i != 0; i >>= 1) {
				if ((i & 1) != 0) {
					children[j].writeNode(os);
				}
				j++;
			}
			writeLong(out, childBits);
			writeThree(out, os.size());
			out.write(os.toByteArray());
		}

		TrieNode addSuffix(String word, int i, long wordBits) {
			if (i == word.length()) {
				childBits |= wordBits;
			} else {
				int ci = LettersMap.cutoi(word.charAt(i));

				if ((childBits & (1 << ci)) == 0) {
					childBits |= 1 << ci;
					children[ci] = EMPTY_LEAF;
					tailCount += 1;
				}

				children[ci] = children[ci].addSuffix(word, i + 1, wordBits);

			}

			return this;
		}

		boolean isWord() {
			return (childBits & WORD_BIT) != 0;
		}

		boolean isTail() {
			return (childBits & LEAF_BIT) != 0;
		}

		private boolean checkAgainstMask(long wordMask) {
			return (wordMask & childBits) != 0;
		}

		protected TrieNode childAt(int i) {
			return children[i];
		}

		boolean isWord(String w, int i, long wordMask) {
			if (i == w.length()) {
				return checkAgainstMask(wordMask);
			}
			int ci = LettersMap.cutoi(w.charAt(i));
			if ((childBits & (1 << ci)) == 0) {
				return false;
			}
			return childAt(ci).isWord(w, i + 1, wordMask);

		}

	}

	/**
	 * The TrieLeaf is a TrieNode that has no children.
	 */
	protected class TrieLeaf extends TrieNode {
		TrieLeaf(long cBits) {
			super(cBits | LEAF_BIT);
		}

		TrieLeaf() {
			super();
		}

		TrieNode addSuffix(String word, int i, long wordBits) {
			if (i == word.length()) {
				return processWordBits(childBits | wordBits);
			} else {
				TrieNode t = new TrieNode(childBits & (~LEAF_BIT));
				tailCount -= 1;
				return t.addSuffix(word, i, wordBits);
			}
		}

		TrieNode processWordBits(long wordBits) {
			if ((wordBits & WORD_BIT) == WORD_BIT)
				return WORD_LEAF;
			if ((wordBits & LEAF_BIT) == LEAF_BIT)
				return EMPTY_LEAF;
			return null;
		}

		void writeNode(OutputStream out) throws IOException {
			out.write((int) (childBits >> 32));
		}
	}

	public static byte countBits(long b) {
		byte c = 0;
		for (b &= LETTER_MASK; b > 0; b >>= 1)
			if ((b & 1) != 0)
				c++;

		return c;
	}

	public void write(OutputStream out) throws IOException {

		root.writeNode(out);

		out.close();
	}

	private void recursiveSolver(TransitionMap m, WordFilter filter,
			TrieNode node, int pos, long unUsed, StringBuilder prefix,
			LinkedHashMap<String, Solution> ret) {

		if (node.isWord()) {
			// String w = prefix.toString();
			String w = new String(prefix);
			long mask = ~unUsed | (1L << pos);
			if (filter == null) {
				ret.put(w, new Solution(w, mask));
			} else if (filter.isWord(w)) {
				ret.put(w, new Solution(w, mask));
			}
		}

		if (node.isTail()) {
			return;
		}

		unUsed &= ~(1L << pos);
		long available = unUsed & m.transitions(pos);

		if (available == 0)
			return;

		for (int i = 0; i < m.getSize(); i++) {
			if ((available & (1L << i)) == 0)
				continue;

			int value = LettersMap.cutoi(m.valueAt(i));
			if ((node.childBits & (1 << value)) == 0)
				continue;

			prefix.append(LettersMap.itouc(value));

			recursiveSolver(m, filter, node.childAt(value), i, unUsed, prefix,
					ret);

			prefix.deleteCharAt(prefix.length() - 1);
		}

	}

	public LinkedHashMap<String, Solution> solver(TransitionMap m) {
		return solver(m, null);
	}

	public LinkedHashMap<String, Solution> solver(TransitionMap m,
			WordFilter filter) {
		LinkedHashMap<String, Solution> ret = new LinkedHashMap<String, Solution>();
		StringBuilder prefix = new StringBuilder(m.getSize() + 1);

		long unused = 0;
		for (int i = 0; i < m.getSize(); i++) {
			unused <<= 1;
			unused++;
		}

		for (int i = 0; i < m.getSize(); i++) {
			int value = LettersMap.cutoi(m.valueAt(i));
			if ((root.childBits & (1 << value)) == 0)
				continue;

			prefix.append(LettersMap.itouc(value));

			recursiveSolver(m, filter, root.childAt(value), i, unused, prefix,
					ret);

			prefix.deleteCharAt(prefix.length() - 1);

		}

		return ret;
	}


}
